/*
 * File:   binary_tree.c
 * Author: aishwarya
 *
 * Created on March 19, 2011, 4:15 PM
 * Binary Search Tree Implementation
 */

#include "binary_tree.h"

/*
Returns: node with minimum <key>
 */
tree_node* bst_minimum(tree_node* r) {
    while (r->left != NULL)
        r = r->left;
    return r;
}

/*
Returns: node with maximum <key>
 */
tree_node* bst_maximum(tree_node* r) {
    while (r->right != NULL)
        r = r->right;
    return r;
}

/*
Returns: successor of node r
 */
tree_node* bst_successor(BST *t, tree_node *r) {
    tree_node * p;

    if (r->right != NULL)
        return bst_minimum(r->right);

    p = r->parent;
    while (p != NULL && t->_keycmpfn(r->data, p->right->data) == 0) {
        r = p;
        p = r->parent;
    }

    return p;
}

/*
Bookkeeping functions
 */
void _bst_clean(BST *t, tree_node *r) {
    if (r == NULL)
        return;

    if (r->left) _bst_clean(t, r->left);
    if (r->right) _bst_clean(t, r->right);

    if (t->_delnodefn)
        t->_delnodefn(r->data);
    free(r);
}

/*
Deletes a BST, removing all the nodes.
 */
void bst_clean(BST *t) {
    LOG(LOG_DBG, "Deleting binary search tree");
    if (t->root) {
        _bst_clean(t, t->root);
        free(t->root);
        t->root = NULL;
    }
}

/*
Looks for a node in BST.
Returns: Pointer to the node, if key matches.
                 Else returns a NULL pointer.
 */
tree_node* _bst_search(BST *t, void *data) {
    tree_node * r = t->root;
    int i;

    while (r != NULL) {
        i = t->_keycmpfn(data, r->data);
        if (i == 0) break;
        if (i == -1)
            r = r->left;
        else r = r->right;
    }

    return r;
}

int bst_search(BST *t, void *data) {
    tree_node * r = _bst_search(t, data);
    if (r->data != NULL)
        return 1;
    return 0;
}

/*
If <key> already exists, then update its occurrence in tree.
Else adds the new <key>.
Returns: Pointer to the node with <key>.
 */
int bst_insert(BST *t, void *data) {
    tree_node * n, *p = NULL, *x = t->root;

    while (x != NULL) {
        p = x;
        if (t->_keycmpfn(data, x->data) < 0) x = x->left;
        else if (t->_keycmpfn(data, x->data) > 0) x = x->right;
        else {
            t->_printfn(x->data);
            return 1;
        }
    }

    /* Allocate new node for key */
    n = (tree_node *) malloc(sizeof (tree_node));

    n->data = malloc(t->e_size);
    t->_datacpyfn(n->data, data);

    n->left = n->right = NULL;
    n->parent = p;

    /* BST was empty */
    if (p == NULL)
        t->root = n;
    else if (t->_keycmpfn(n->data, p->data) < 0)
        p->left = n;
    else p->right = n;

    return 1;
}

/*
Deletes a node with key <key>
Returns: 0, if <key> not found, else 1.
 */
int bst_delete(BST *t, void *data) {
    tree_node *x, *y, *z;

    LOG(LOG_DBG, "Deleting node");
    /* Find node with <key> */
    z = _bst_search(t, data);

    if (z == NULL)
        return 0;

    /* Which node is actually removed depends on how many children z has
       CLRS, Section 12.3, Figure 12-4 */

    y = (z->left == NULL || z->right == NULL) ? z : bst_successor(t, z);
    x = (y->left != NULL) ? y->left : y->right;

    if (x != NULL) x->parent = y->parent;

    if (y->parent == NULL)
        t->root = x;
    else if (t->_keycmpfn(y->data, y->parent->left->data) == 0)
        y->parent->left = x;
    else y->parent->right = x;

    if (t->_keycmpfn(y->data, z->data))
        /* Copy y's satellite date into z */
        t->_datacpyfn(z->data, y->data);

    return 1;
}

/*
Inorder traversal of the root.
 */
void __bst_inorder(BST *t, tree_node * r) {
    if (r != NULL) {
        __bst_inorder(t, r->left);
        t->_printfn(r->data);
        __bst_inorder(t, r->right);
    }
}

void bst_inorder(BST *t) {
    LOG(LOG_DBG, "Inorder traversal of binary search tree");
    __bst_inorder(t, t->root);
}

/*
Initializes a BST
 */
void bst_init(BST *t, size_t e_size, KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p) {
    t->root = NULL;
    t->e_size = e_size;

    t->_keycmpfn = k;
    t->_datacpyfn = d;
    t->_delnodefn = n;
    t->_printfn = p;
}

